/*
    created: 2023/4/10
    filename: Main.c
    author: 李东霖
    purpose: 单链表的实现和操作的实现
*/

#include"forward_list.h"
// 1. 反向输出带头结点的单链表的全部结点的值
void ReDispNode(LNode *p)
{
    if(p == NULL) return;
    ReDispNode(p->next);
    printf("%d  ",p->data);
}
void ReDispList(LinkList head)
{
    ReDispNode(head->next);
}


// 2. 找出带头结点的单链表倒数第K（K>0）个结点
LNode* GetRListNode(LinkList head,int k)
{
    LNode *slow = head;
    LNode *fast = head;
    while(k != 0 && fast != NULL)
    {
        --k;
        fast = fast->next;
    }
    while(fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;

}

// 3. 判断链表是否有环，并找到入口
LNode* IsCirList(LinkList head)
{
    //len = (n-1)r + t
    LNode *slow = head;
    LNode *fast = head;
    //空指针和空表不能做下面的while
    while(fast != NULL && fast->next != NULL && slow != fast)
    {
        slow = slow->next;
        fast = fast->next->next;
    } 
    //没有环
    if(fast != NULL || fast->next == NULL) return NULL;
    slow = head;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}


// 4. 找出两个汇聚单链表的公共结点  
LNode* GetNode(LinkList head1,LinkList head2)
{
    int len1 = LengthList(head1);
    int len2 = LengthList(head2);
    LNode *p,*q;
    for(p = head1;len1<len2;len2--) q =q->next; 
    for(q = head2;len1>len2;len1--) p =p->next; 

    while(1)
    {
        if(p == q) break;
        q = q->next;
        p = p->next;
        if(p == NULL) return NULL;
    }
    return q;
}


// 5. 线性表L= （a1.....an）采用带头结点的单链表存储，设计一个空间复杂度为O(1)且时间高效的算法，
//    重新排列L = (a1,an,a2,an-1.......)
void Repailie(LinkList head)
{
    LNode* fast = head;
    LNode* slow = head;     
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    //slow指向前半段链表的最后一个结点 我们反转后面的链表
    //调用ReverseList 或者再写一遍
    LNode *ss = slow->next;      // 反转结点。
    LNode *ssnext;  // 反转结点的下个结点
    slow->next = NULL;
    LNode* p = slow;
    while(ss != NULL)
    {
        ssnext = ss->next;
        ss->next == p->next;
        p->next = ss;
        ss = ssnext;
    }
    //DispList(head);
    
    p = head->next;
    ss = slow->next;
    slow->next = NULL;
    while(ss != NULL)
    {
        ssnext = ss->next;
        ssnext->next = p->next;
        p->next = ss;
        ss = ssnext;
        p = p->next->next;
    }
}

// 6.将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度 O(1)。
void reverseBetween(LinkList head, int m, int n) 
{
    if (head == NULL || head->next == NULL) return;
    LNode* p = head;
    int pos = 0;
    //找到m的前驱
    while (p != NULL && pos != m - 1) 
    {
        p = p->next;
        ++pos;
    }
    // printf("%d \n",p->data);
    //找到n结点
    pos = 0;
    LNode* q = p;
    while(q != NULL && pos != n-m+2)
    {
        q = q->next;
        ++pos;           
    }
    // printf("%d \n",q->data);
    //反转m到n
    LNode* temp = p->next;
    LNode* tempnext;
    p->next =NULL;

    //反转p q
    while(temp != q)
    {
        // printf("%d \n",temp->data);
        tempnext = temp->next;
        temp->next = p->next;
        p->next = temp;
        temp = tempnext;
    }
}
int main()
{
    LinkList head = InitList1();
    for(int i = 0;i != 5;++i)
    {
        InsertList(head,1,&i);
    }
    DispList(head);
    printf("\n");
    reverseBetween(head,1,5);
    DispList(head);
    printf("\n");   





    // ReDispList(head);
    // LNode* p = GetRListNode(head,3);
    // printf("%d ",p->data);


    // ElemType elem = 100;
    // Push_Back(head,&elem);
    // DispList(head);
    // printf("\n");

    // InsertList(head,5,&elem);
    // Push_Front(head,&elem);
    
    // // ClearList(head);
    // Push_Front(head,&elem);

    // DispList(head);
    // printf("length = %d \n",LengthList(head));

    // Pop_Back(head);
    // Pop_Front(head);
    // DeleteNode(head,2);
    // DispList(head);
    // printf("length = %d \n",LengthList(head));

    // elem = 1;
    // LNode* pp = LocateElem(head,&elem);
    // printf("data = %d\n",pp->data);
    // elem = 500;
    // InsertPriorNode(pp,&elem);
    // DispList(head);
    // printf("length = %d \n",LengthList(head)); 

  
    // pp = LocateNode(head,3);
    // printf("data = %d\n",pp->data);
    // InsertNextNode(pp,&elem);
    // DispList(head);
    // printf("length = %d \n",LengthList(head));

    // ReverseList(head);
    // DispList(head);









    return 0;
}